/**
 * @author hewei
 * @version 1.0
 * @description: 1774. 最接近目标价格的甜点成本
 * @date 2022/10/13 15:26
 */

public class ClosestCost {

    int[] toppingCosts;
    int ans;
    int target;
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        this.toppingCosts = toppingCosts;
        ans = Integer.MAX_VALUE;
        this.target = target;
        for (int baseCost : baseCosts) {
            process(0, baseCost);
        }
        return ans;
    }

    public void process(int i, int sum) {
        if (i == toppingCosts.length) {
            int abs = Math.abs(sum - target);
            int temp = Math.abs(ans - target);
            if (abs == temp) {
                ans = Math.min(ans, sum);
            } else if (abs < temp) {
                ans = sum;
            }
            return;
        }
        process(i + 1, sum);
        process(i + 1, sum + toppingCosts[i]);
        process(i + 1, sum + toppingCosts[i] + toppingCosts[i]);
    }
}
